The present invention relates generally to systems and methods for performing Reed-Solomon encoding and decoding, and in particular to semi-parallel Reed-Solomon encoders and decoders.
The transmission of information is of great importance to computing networks, from a local area network to the Internet. In thriving computing networks, the demands for a faster, more reliable and cost-effective manner of transmitting information are constantly increasing. However, satisfying these demands is difficult and replete with obstacles. These obstacles include bandwidth limitations, total system component costs, reliability and quality of service.
Conventional fiber optic networks, generally conforming to standards such as synchronous optical network (SONET) and synchronous digital hierarchy (SDH), are widely prevalent and allow for increasingly greater transmission. Also, with the advent of time division multiplexing (TDM) components, the conventional fiber optic bandwidth is quadrupled. However, as new technologies and services develop in video, high resolution graphics and other types of applications requiring tremendous amounts of data, the bandwidth provided by TDM is being quickly exhausted.
Also, as the demand for faster service and the dependence of computing networks on the transmission of information grows, the reliability on the information becomes critical. Multiple types of transmission schemes have been developed to ensure data trustworthiness. One common and widely utilized transmission scheme, especially in the high-speed realm of fiber optics, is Reed-Solomon (RS) encoding and decoding. However, serial operation of RS encoding and decoding acts, to an extent, as a bottleneck in data transmission systems that use high data rates. On the other hand, fully parallel operation of RS encoding and decoding provides better time performance under high data rates, but is often costly and complex, and includes high VLSI gate counts and increased power usage requirements.
The present invention provides a semi-parallel Reed-Solomon encoder and decoder. In one embodiment, the present invention comprises a method of performing semi-parallel encoding and decoding using an (n,k) code. In one embodiment the method comprises sequentially providing sets of a plurality of information symbols to an encoder, the sets of the plurality of information symbols forming an information word. On each set of the information symbols Galois field multiplication is sequentially performed to form intermediate terms. Combining the intermediate terms results in, or forms, at least some of the symbols of the code word. The method further comprises sequentially generating n-k syndromes, and determining an error locator polynomial using the n-k syndromes. Further, in one embodiment, the method comprises evaluating a plurality of roots of the error locator polynomial using a plurality of polynomial evaluators, each polynomial evaluator evaluating a plurality of the roots of the error locator polynomial.
In another embodiment, a method of the present invention comprises encoding a data stream forming an information vector, the data stream comprising a plurality of information symbols, with a method comprising providing a first set of information symbols to a Galois field multiplier, the first set of information symbols being less than the plurality of information symbols. Further, the method comprises performing Galois field multiplication on the first set of information symbols to form a first set of code words, and providing a second set of information symbols to the Galois field multiplier and performing Galois field multiplication on the second set of information symbols.